package com.leetcode.algorithm.y22.m07.w4;

/**
 * 707. 设计链表
 * 
 * https://leetcode.cn/problems/design-linked-list/
 * 
 * @author jie.deng
 *
 */
public class MyLinkedList03 {

	private DoublyListNode head;
	private DoublyListNode tail;
	private int cnt;

	public MyLinkedList03() {
		head = new DoublyListNode(0, null, null);
		tail = new DoublyListNode(0, null, null);
		head.next = tail;
		tail.prev = head;
	}

	public int get(int index) {
		if (index < 0 || index >= this.cnt) {
			return -1;
		}
		DoublyListNode node = getNodeAtIndex(index);
		return node.val;
	}

	/**
	 * 根据索引查找节点
	 * 
	 * @param index [0,cnt-1]
	 * @return
	 */
	private DoublyListNode getNodeAtIndex(int index) {
		assert index >= 0 && index < this.cnt;
		if (index < (this.cnt << 1)) {
			return leftNodeAtIndex(index);
		}
		return rightNodeAtIndex(this.cnt - index);
	}

	private DoublyListNode leftNodeAtIndex(int index) {
		DoublyListNode cur = head;
		while (index >= 0) {
			cur = cur.next;
			index--;
		}
		return cur;
	}

	private DoublyListNode rightNodeAtIndex(int index) {
		DoublyListNode cur = tail;
		while (index >= 0) {
			cur = cur.prev;
			index--;
		}
		return cur;
	}	

	/**
	 * 查找前一个节点
	 * 
	 * @param index [0,cnt]
	 * @return
	 */
	private DoublyListNode getPrevNode(int index) {
		assert index >= 0 && index <= this.cnt;
		if (index == 0) {
			return head;
		}
		return getNodeAtIndex(index - 1);
	}

	public void addAtHead(int val) {
		addAtIndex(0, val);
	}

	public void addAtTail(int val) {
		addAtIndex(this.cnt, val);
	}

	public void addAtIndex(int index, int val) {
		if (index > this.cnt) {
			return;
		}
		if (index <= 0) {
			index = 0;
		}

		DoublyListNode cur = getPrevNode(index);
		DoublyListNode node = new DoublyListNode(val, cur, cur.next);
		if (cur.next != null) {
			cur.next.prev = node;
		}
		cur.next = node;
		this.cnt++;
	}

	public void deleteAtIndex(int index) {
		if (index < 0 || index >= this.cnt) {
			return;
		}
		DoublyListNode cur = getPrevNode(index);
		cur.next = cur.next.next;
		if (cur.next != null) {
			cur.next.prev = cur;
		}
		this.cnt--;
	}

	private static class DoublyListNode {
		int val;
		DoublyListNode prev;
		DoublyListNode next;

		DoublyListNode(int val, DoublyListNode prev, DoublyListNode next) {
			this.val = val;
			this.prev = prev;
			this.next = next;
		}
	}
}